import java.util.HashMap;

// 用类描述实现前缀树。哈希版
public class TrieTree2 {
    class TrieNode{
        public int pass;
        public int end;
        public HashMap<Integer,TrieNode> nexts;

        public TrieNode(){
            pass = 0;
            end = 0;
            nexts = new HashMap<>();
        }
    }

    private TrieNode root;

    public TrieTree2(){
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode cur = root;
        cur.pass++;

        for(int i = 0, path; i < word.length(); i++){
            path = word.charAt(i) - 'a';

            if(!cur.nexts.containsKey(path)){
                cur.nexts.put(path,new TrieNode());
            }
            cur = cur.nexts.get(path);
            cur.pass++;
        }
        cur.end++;
    }

    // 如果之前word插入过前缀树，那么此时删掉一次
    // 如果之前word没有插入过前缀树，那么什么也不做
    public void erase(String word) {
        if(countWordsEqualTo(word) == 0){  //不存在当前这个字符串直接结束方法
            return;
        }

        TrieNode cur = root;
        cur.pass--;

        for(int i = 0, path; i < word.length(); i++){
            path = word.charAt(i) - 'a';

            if(--cur.nexts.get(path).pass == 0){
                cur.nexts.remove(path);
                return;
            }
            cur = cur.nexts.get(path);
        }
        cur.end--;
    }

    // 查询前缀树里，word单词出现了几次
    public int countWordsEqualTo(String word) {
        TrieNode cur = root;

        for(int i = 0, path; i < word.length(); i++){
            path = word.charAt(i) - 'a';

            if(!cur.nexts.containsKey(path)){
                return 0;
            }
            cur = cur.nexts.get(path);
        }
        return cur.end;
    }

    // 查询前缀树里，有多少单词以pre做前缀
    public int countWordsStartingWith(String pre) {
        TrieNode cur = root;;

        for(int i = 0, path; i < pre.length(); i++){
            path = pre.charAt(i) - 'a';
            if(!cur.nexts.containsKey(path)){
                return 0;
            }
            cur = cur.nexts.get(path);
        }
        return cur.pass;
    }

}
